package merge_sort

import (
	"learning/gooop/sorting"
)

type tMergeSort struct {}

func newMergeSort() sorting.ISorter {
	return &tMergeSort{}
}

func (me *tMergeSort) Sort(data []interface{}, comparator sorting.CompareFunction) []interface{} {
	if data == nil {
		return nil
	}

	size := len(data)
	if size <= 1 {
		return data
	}

	var result []interface{} = nil
	buffer := make([]interface{}, size)
	for span := 1; span <= size;span *= 2 {
		for i := 0;i < size;i += span * 2 {
			merge(size, data, i, i + span, span, buffer, i, comparator)
		}

		result = buffer
		data, buffer = buffer, data
	}

	if result == nil {
		result = data
	}

	return result
}

// 合并data数组中的两个子序列: [q1:q1+span), [q2:q2+span), 到目标数组result的offset位置
func merge(size int, data []interface{}, q1 int, q2 int, span int, result []interface{}, offset int, comparator sorting.CompareFunction) {
	e1 := min(q1 + span, size)
	e2 := min(q2 + span, size)
	j := -1
	k := -1

	for i := 0;i < span*2;i++ {
		if q1 >= e1 {
			j = q2
			k = e2

		} else if q2 >= e2 {
			j = q1
			k = e1
		}

		if j >= 0 {
			for p := j;p < k;p++ {
				result[offset] = data[p]
				offset++
			}
			break
		}

		v1 := data[q1]
		v2 := data[q2]

		if lessEqual(v1, v2, comparator) {
			result[offset] = v1
			q1++
		} else {
			result[offset] = v2
			q2++
		}
		offset++
	}
}

func lessEqual(v1 interface{}, v2 interface{}, comparator sorting.CompareFunction) bool {
	return comparator(v1, v2) != sorting.GREATER
}

func min(a,b int) int {
	if a <= b {
		return a
	} else {
		return b
	}
}

var MergeSort = newMergeSort()